/**
*  @file ReverseLink.c
 *  @desc 实现一个双向链表的基本操作，包括插入、删除、反转、打印等功能
 *        支持通过尾插法创建链表并在主函数中验证链表反转功能。
 *  @author WangBlue(wangjiping596@gmail.com)
 *  @date 2025-07-23 10:20
 *  @version 1.0
 */

#include <stdio.h>
#include <stdlib.h>

// ------------------------- 结构体定义 -------------------------

/**
 * @brief 双向链表结点结构体
 */
typedef struct node {
    int data;               ///< 数据域
    struct node *next;      ///< 指向下一个节点
    struct node *pre;       ///< 指向上一个节点
} node, *link;

// ------------------------- 基础操作 -------------------------

/**
 * @brief 创建一个带数据的新节点
 * @param value 节点的数据
 * @return 创建成功返回新节点指针，否则返回 NULL
 */
link createNode(int value) {
    link newNode = (link) malloc(sizeof(node));
    if (newNode == NULL) return NULL;
    newNode->next = NULL;
    newNode->pre  = NULL;
    newNode->data = value;
    return newNode;
}

/**
 * @brief 初始化一个空链表（仅创建头结点）
 * @param head 指向链表头指针的指针
 */
void initNode(link *head) {
    link newNode = (link) malloc(sizeof(node));
    if (newNode == NULL) return;
    newNode->next = NULL;
    newNode->pre  = NULL;
    newNode->data = 0; // 头结点的数据不使用
    *head = newNode;
}

// ------------------------- 插入操作 -------------------------

/**
 * @brief 头插法插入结点
 * @param head 链表头指针
 * @param value 要插入的数据值
 */
void istHead(link head, int value) {
    link newNode = createNode(value);
    if (newNode == NULL) return;

    newNode->next = head->next;
    newNode->pre = head;

    if (head->next != NULL) {
        head->next->pre = newNode;
    }
    head->next = newNode;
}

/**
 * @brief 尾插法插入结点
 * @param head 链表头指针
 * @param value 要插入的数据值
 */
void istTail(link head, int value) {
    link cur = head;
    while (cur->next != NULL) {
        cur = cur->next;
    }

    link newNode = createNode(value);
    if (newNode == NULL) return;

    cur->next = newNode;
    newNode->pre = cur;
}

// ------------------------- 打印链表 -------------------------

/**
 * @brief 正向打印链表数据（跳过头结点）
 * @param head 链表头指针
 */
void printList(link head) {
    if (head == NULL || head->next == NULL) return;

    link cur = head->next;
    while (cur != NULL) {
        printf("value is %d\n", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

// ------------------------- 删除操作 -------------------------

/**
 * @brief 删除指定位置的结点（位置从 1 开始）
 * @param head 链表头指针
 * @param pos 要删除的位置（从 1 开始）
 */
void delByPos(link head, int pos) {
    if (head == NULL || head->next == NULL) return;

    int idx = 1;
    link cur = head->next;

    while (cur != NULL && idx < pos) {
        cur = cur->next;
        idx++;
    }

    if (cur == NULL) return;

    if (cur->pre != NULL) {
        cur->pre->next = cur->next;
    }
    if (cur->next != NULL) {
        cur->next->pre = cur->pre;
    }

    free(cur);
}

/**
 * @brief 在指定位置插入数据
 *  @param head 链表头指针
 *  @param value 要插入的值
 * @param pos 要删除的位置（从 1 开始）
 */
void insertByPos(link head, int value, int pos) {
    if (head == NULL || pos < 1) return;

    link cur = head;
    int idx = 0;
    while (cur != NULL && idx < pos - 1) {
        cur = cur->next;
        idx++;
    }

    if (cur == NULL) return;

    link newNode = createNode(value);
    if (newNode == NULL) return;

    newNode->next = cur->next;
    newNode->pre = cur;

    if (cur->next != NULL) {
        cur->next->pre = newNode;
    }
    cur->next = newNode;
}
/**
 * @brief 反转双向链表（带头节点）
 * @param head 链表的头指针（必须带头节点，且不为NULL）
 * @note 反转的是从 head->next 开始的链表部分，头节点本身不动。
 */
void reverseLink(link head) {
    // 若链表为空 或 仅头节点一个元素（即没有实际数据），则无需反转
    if (head == NULL || head->next == NULL) return;

    // 当前正在处理的节点
    link cur = head->next;

    // 将头节点与实际数据断开
    head->next = NULL;

    // 遍历原链表，逐个将节点插入到头节点之后，实现逆序
    while (cur != NULL) {
        // 保存当前节点的下一个节点，以免断链
        link next = cur->next;

        // 当前节点插入到头节点之后
        cur->next = head->next;  // 指向原来的第一个节点
        cur->pre = head;         // 当前节点的前驱指向头节点

        // 若当前已有节点被插入过（head->next非空），更新原第一个节点的pre指针
        if (head->next != NULL) {
            head->next->pre = cur;
        }

        // 更新头节点的next指针，指向当前插入的节点
        head->next = cur;

        // 继续处理下一个节点
        cur = next;
    }
}

/**
 * @brief 主函数，测试 reverseLink 功能
 */
int main() {
    link head = NULL;

    // 初始化链表头节点
    initNode(&head);

    // 尾插方式创建链表：1 -> 2 -> 3
    istTail(head, 1);
    istTail(head, 2);
    istTail(head, 3);

    // 反转链表：变成 3 -> 2 -> 1
    reverseLink(head);

    // 打印链表内容，期望输出 3 2 1
    printList(head);
}
